package BinaryTree;
/*
 * 二叉树的最大路径和
 * 后序遍历, 当前根节点的最大路径和,往上递归, 维护一个最大值的全局变量
 *
 * */
public class MaxPathSum124 {
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // 这里不能用max来接受,因为max是全局最大值(动态的),而不是最后根节点的路径和
        dfs(root);
        return max;
    }

    int dfs(TreeNode root) {
        if(root==null)return 0;
        // 如果子树的和为负, 则应该置零, 表示最大路径不包含子树
        int l=Math.max(0,dfs(root.left));
        int r=Math.max(0,dfs(root.right));
        max=Math.max(max,root.val+l+r);
        return Math.max(l,r)+root.val;
    }
}
